package com.hdu.other.tanxin;

public class lc517 {
    class Solution {
        public int findMinMoves(int[] machines) {
            int len = machines.length;
            int sum = 0;
            for (int i = 0; i < len; i++) {
                sum += machines[i];
            }
            if (sum % len != 0) {
                return -1;
            }
            int avg = sum / len;
            int leftNeed = 0;
            int leftSum = 0;
            int rightNeed = 0;
            int ans = Integer.MIN_VALUE;
            for (int i = 0; i < len; i++) {
                leftNeed = avg * i - leftSum;
                rightNeed = avg * (len - 1 - i - 1 + 1) - (sum - leftSum - machines[i]);
                int curAns = 0;
                if (leftNeed > 0 && rightNeed > 0) {
                    curAns = leftNeed + rightNeed;
                } else {
                    curAns = Math.max(Math.abs(leftNeed), Math.abs(rightNeed));
                }
                ans = Math.max(ans, curAns);
                leftSum += machines[i];
            }
            return ans;
        }
    }
}
